/**
 * 该模块定义了一些常用的数组操作。
 * License: BSD
 * Authors: Lucifer (786325481@QQ.com)
 * Copyright: Copyright (C) 2008 Lucifer. All rights reserved.
 */

module system.Array;

import system.Traits;
import system.Exception;
import system.collections.IComparer;
import system.collections.Comparer;
import system.collections.EqualityComparer;

import system.runtime.c.string;

version(unittest)
{
	import system.Random; //only for unit test
}

/**
 * 提供一些数组常用操作。
 */
public class Array
{
    private this() {}

	/* **********************************************************************************
     * 为什么几个比较方法会有两段几乎相同的代码，无它，只为了性能
     * 在我的试验中，由于内联，函数调用，参数传值等开销，两段代码的性能大概有2~3倍的差距
	 * 对于值类型可能结果是这样，引用类型性能提高有限，但也快不少。

     * 为什么没有指定数组范围的方法，因为D语言数组自带了切片功能

     * 因为D语言 delegate 和 function，所以所有牵涉到委托的地方都会有两个方法重载
	 * ***********************************************************************************/


    /**
     * 使用指定的 IComparer(T) 泛型接口，在整个一维排序 Array 中搜索值。
     * Params: array = 要搜索的从零开始的一维排序 Array。
     *         value = 要搜索的对象。
     *         comparer = 比较元素时要使用的 IComparer(T) 实现。
     * Returns: 如果找到 value，则为 array 中的指定 value 的索引。
     *          如果找不到 value，且value小于数组内任何元素值时，返回数组内第一个大于value的元素索引值的按位求反值。
	 *          如果找不到 value，且value大于数组内任何元素值时，返回数组内最后一个元素索引值的按位求反值。
	 *          如果数组的长度为 0 ，则返回 -1 。
     * Throws: InvalidOperationException, 当 value 没有正确实现 opCmp 时
     */
    public static int binarySearch(T)(T[] array, T value, IComparer!(T) comparer = null)
    in
    {
        assert( array !is null );
    }
    body
    {
		if(array.length == 0)
			return -1;

        int mid;
        int low = 0;
        int high = array.length - 1;

        if( comparer is null )
        {
            static if( IsIntegerType!(T) ||
            		IsCharType!(T) ||
            		( is(T == struct) && is(typeof(T.opCmp)) && is(typeof(T.opEqual)) ))
            {
                while( low < high )
                {
                    mid = low +( high - low) / 2;
                    if( array[mid] < value )
                        low = mid + 1;
                    else
                        high = mid;
                }
                if( array[low] == value )
                    return low;
                return ~low;
            }
            else
            {
                comparer = DefaultComparer!(T).getInstance();
            }
        }

        while( low < high )
        {
            mid = low +( high - low) / 2;
            try
            {
                if( comparer.compare(array[mid], value) < 0 )
                    low = mid + 1;
                else
                    high = mid;
            }
            catch(Exception e)
            {
                throw new InvalidOperationException(e.msg, e);
            }
        }

        if( comparer.compare(array[low], value) == 0 )
            return low;

        return ~low;
    }
    /**
     * 将 Array 中的一系列元素设置为零、false 或 空引用，具体取决于元素类型。
     * Comments: 此方法仅清除元素的值，而不删除元素本身。
     */
    public static void clear(T)(T[] array)
    in
    {
        assert(array !is null);
    }
    body
    {
        memset(array.ptr, 0, T.sizeof * array.length);
    }

    /**
     * 从指定的源索引开始，复制 Array 中的一系列元素，将它们粘贴到另一 Array 中。
     * Params: sourceArray = 它包含要复制的数据。
     *         destinationArray = 它接收数据。
     *         size -> 它表示要复制的元素数目。
     * Comments: 它等同于C/C++函数 memmove，而不是 memcpy。
     */
    public static void copy(T)(T[] sourceArray, T[] destinationArray, size_t size)
    in
    {
        assert(sourceArray !is null);
        assert(destinationArray !is null);
        //assert(size > 0);
    }
    body
    {
        memmove(destinationArray.ptr, sourceArray.ptr, T.sizeof * size);
    }

    /**
     * 将一种类型的数组转换为另一种类型的数组。
     * Params: array = 要转换为目标类型的从零开始的一维 Array。
     *         converter = 用于将每个元素从一种类型转换为另一种类型.
     * Comments: converter 是对方法的委托，它将对象转换为目标类型。
     *           array 的元素被逐个传递给 Converter，转换后的元素保存在新数组中。
     *           源 array 保持不变。
     *           此方法的运算复杂度为 O(n)，其中 n 是 array 的 length。
     */
    public static TOutput[] convertAll(TInput, TOutput)(TInput[] array, TOutput delegate(TInput) converter)
    in
    {
        assert( array !is null );
        assert( converter !is null );
    }
    body
    {
        TOutput[] result = new TOutput[array.length];
        for(auto i = 0; i < array.length; i++)
        {
            result[i] = converter(array[i]);
        }
        return result;
    }
    /// ditto
    public static TOutput[] convertAll(TInput, TOutput)(TInput[] array, TOutput function(TInput) converter)
    in
    {
        assert( array !is null );
        assert( converter !is null );
    }
    body
    {
        TOutput[] result = new TOutput[array.length];
        for(auto i = 0; i < array.length; i++)
        {
            result[i] = converter(array[i]);
        }
        return result;
    }
    /**
     * 确定指定数组包含的元素是否与指定谓词定义的条件匹配。
     * Params: array = 要搜索的从零开始的一维 Array。
     *         match = 定义要搜索的元素的条件。
     * Returns: 如果 array 包含一个或多个元素与指定谓词定义的条件匹配，则为 true；否则为 false。
     * Comments: match 是对方法的委托，如果传递给它的对象与委托中定义的条件匹配，则该方法返回 true。
     *           array 的元素被逐个传递给 委托，找到一个匹配项时处理就会停止。
     *           此方法的运算复杂度为 O(n)，其中 n 是 array 的 length。
     */
    public static bool exists(T)(T[] array, bool delegate(T) match)
    in
    {
        assert(array !is null );
        assert(match !is null);
    }
    body
    {
        for(auto i = 0; i < array.length; i++)
        {
            if( match(array[i]) )
                return true;
        }
        return false;
    }
    /// ditto
    public static bool exists(T)(T[] array, bool function(T) match)
    in
    {
        assert(array !is null );
        assert(match !is null);
    }
    body
    {
        for(auto i = 0; i < array.length; i++)
        {
            if( match(array[i]) )
                return true;
        }
        return false;
    }
    /**
     * 搜索与指定谓词定义的条件匹配的元素，然后返回整个 Array 中的第一个匹配项。
     * Params: array = 要搜索的从零开始的一维 Array。
     *         match = 定义要搜索的元素的条件。
     * Returns: 如果找到与指定谓词定义的条件匹配的第一个元素，则为该元素；否则为类型 T 的默认值。
     * Comments: match 是对方法的委托，如果传递给它的对象与委托中定义的条件匹配，则该方法返回 true。
     *           array 的元素被逐个传递给 委托，找到一个匹配项时处理就会停止。
     *           此方法的运算复杂度为 O(n)，其中 n 是 array 的 length。
     */
    public static T find(T)(T[] array, bool delegate(T) match)
    in
    {
        assert(array !is null);
        assert(match !is null);
    }
    body
    {
        for(auto i = 0; i < array.length; i++)
        {
            if( match(array[i]) )
                return array[i];
        }
        return T.init;
    }
    /// ditto
    public static T find(T)(T[] array, bool function(T) match)
    in
    {
        assert(array !is null );
        assert(match !is null);
    }
    body
    {
        for(auto i = 0; i < array.length; i++)
        {
            if( match(array[i]) )
                return array[i];
        }
        return T.init;
    }
    /**
     * 检索与指定谓词定义的条件匹配的所有元素。
     * Params: array = 要搜索的从零开始的一维 Array。
     *         match = 定义要搜索的元素的条件。
     * Returns: 如果找到一个其中所有元素均与指定谓词定义的条件匹配的 Array，则为该数组；否则为一个空 Array。
     * Comments: match 是对方法的委托，如果传递给它的对象与委托中定义的条件匹配，则该方法返回 true。
     *           array 的元素被逐个传递给 委托，找到一个匹配项时处理就会停止。
     *           此方法的运算复杂度为 O(n)，其中 n 是 array 的 length。
     */
    public static T[] findAll(T)(T[] array, bool delegate(T) match)
    in
    {
        assert(array !is null );
        assert(match !is null);
    }
    body
    {
        auto pos = 0;
        T[] newArray = new T[array.length];
        for(auto i = 0; i < array.length; i++)
        {
            if( match(array[i]) )
                T[pos++] = array[i];
        }
        newArray.length = pos;
        return newArray;
    }
    /// ditto
    public static T[] findAll(T)(T[] array, bool function(T) match)
    in
    {
        assert(array !is null);
        assert(match !is null);
    }
    body
    {
        auto pos = 0;
        T[] newArray = new T[array.length];
        for(auto i = 0; i < array.length; i++)
        {
            if( match(array[i]) )
                T[pos++] = array[i];
        }
        newArray.length = pos;
        return newArray;
    }

    /**
     * 搜索与指定谓词定义的条件匹配的元素，然后返回整个 Array 中第一个匹配项的从零开始的索引。
     * Params: array = 要搜索的从零开始的一维 Array。
     *         match = 定义要搜索的元素的条件。
     * Returns: 如果找到与 match 定义的条件相匹配的第一个元素，则为该元素的从零开始的索引；否则为 -1。
     * Comments: match 是对方法的委托，如果传递给它的对象与委托中定义的条件匹配，则该方法返回 true。
     *           array 的元素被逐个传递给 委托，找到一个匹配项时处理就会停止。
     *           此方法的运算复杂度为 O(n)，其中 n 是 array 的 length。
     */
    public static int findIndex(T)(T[] array, bool delegate(T) match)
    in
    {
        assert(array !is null );
        assert(match !is null);
    }
    body
    {
        for(auto i = 0; i < array.length; i++)
        {
            if( match(array[i]) )
                return i;
        }
        return -1;
    }
    /// ditto
    public static int findIndex(T)(T[] array, bool function(T) match)
    in
    {
        assert(array !is null );
        assert(match !is null);
    }
    body
    {
        for(auto i = 0; i < array.length; i++)
        {
            if( match(array[i]) )
                return i;
        }
        return -1;
    }
    /**
     * 搜索与指定谓词定义的条件匹配的元素，然后返回整个 Array 中的最后一个匹配项。
     * Params: array = 要搜索的从零开始的一维 Array。
     *         match = 定义要搜索的元素的条件。
     * Returns: 如果找到，则为与指定谓词所定义的条件相匹配的最后一个元素；否则为类型 T 的默认值。
     * Comments: match 是对方法的委托，如果传递给它的对象与委托中定义的条件匹配，则该方法返回 true。
     *           array 的元素被逐个传递给 委托，找到一个匹配项时处理就会停止。
     *           此方法的运算复杂度为 O(n)，其中 n 是 array 的 length。
     */
    public static int findLast(T)(T[] array, bool delegate(T) match)
    in
    {
        assert( array !is null );
        assert( match !is null );
    }
    body
    {
        for(auto i = array.length-1; i >= 0; i--)
        {
            if( match(array[i]) )
                return array[i];
        }
        return T.init;
    }
    /// ditto
    public static int findLast(T)(T[] array, bool function(T) match)
    in
    {
        assert( array !is null );
        assert( match !is null );
    }
    body
    {
        for(auto i = array.length -1 ; i >= 0; i--)
        {
            if( match(array[i]) )
                return i;
        }
        return T.init;
    }
    /**
     * 搜索与指定谓词定义的条件匹配的元素，然后返回整个 Array 中最后一个匹配项的从零开始的索引。
     * Params: array = 要搜索的从零开始的一维 Array。
     *         match = 定义要搜索的元素的条件。
     * Returns: 如果找到与 match 定义的条件相匹配的最后一个元素，则为该元素的从零开始的索引；否则为 -1。
     * Comments: match 是对方法的委托，如果传递给它的对象与委托中定义的条件匹配，则该方法返回 true。
     *           array 的元素被逐个传递给 委托，找到一个匹配项时处理就会停止。
     *           此方法的运算复杂度为 O(n)，其中 n 是 array 的 length。
     */
    public static int findLastIndex(T)(T[] array, bool delegate(T) match)
    in
    {
        assert( array !is null );
        assert( match !is null );
    }
    body
    {
        for(auto i = array.length-1; i >= 0; i--)
        {
            if( match(array[i]) )
                return i;
        }
        return -1;
    }
    /// ditto
    public static int findLastIndex(T)(T[] array, bool function(T) match)
    in
    {
        assert( array !is null );
        assert( match !is null );
    }
    body
    {
        for(auto i = array.length-1; i >= 0; i--)
        {
            if( match(array[i]) )
                return i;
        }
        return -1;
    }

    /**
     * 搜索指定的对象，并返回整个 Array 中第一个匹配项的索引。
     * Params: array = 要搜索的从零开始的一维 Array。
     *         value = 要在 array 中查找的对象。
     * Returns: 如果在整个 array 中找到 value 的匹配项，则为第一个匹配项的从零开始的索引；否则为 -1。
     * Comments: 从 Array 的第一个元素开始向前搜索，到最后一个元素停止搜索。
     */
    public static int indexOf(T)(T[] array, T value)
    in
    {
        assert(array !is null);
    }
    body
    {
        DefaultEqualityComparer!(T) equalityComparer = DefaultEqualityComparer!(T).getInstance();
        for(auto i = 0; i < array.length; i++)
        {
            if( equalityComparer.equals(array[i], value) )
                return i;
        }

        return -1;
    }
    /**
     * 搜索指定的对象，并返回整个 Array 中最后一个匹配项的索引。
     * Params: array = 要搜索的从零开始的一维 Array。
     *         value = 要在 array 中查找的对象。
     * Returns: 如果在整个 array 中找到 value 的匹配项，则为最后一个匹配项的从零开始的索引；否则为 -1。
     * Comments: 在 Array 中从最后一个元素向后开始搜索，并在第一个元素停止搜索。
     */
    public static int lastIndexOf(T)(T[] array, T value)
    in
    {
        assert(array !is null);
    }
    body
    {
        DefaultEqualityComparer!(T) equalityComparer = DefaultEqualityComparer!(T).getInstance();
        for(auto i = array.length-1; i >= 0; i--)
        {
            if( equalityComparer.equals(array[i], value) )
                return i;
        }

        return -1;
    }

    //交换数组内位置
    private static void swap(T)(T* x, T* y)
    {
        T temp = *x;
        *x = *y;
        *y = temp;
    }

    /**
     * 使用指定的 IComparer(T) 泛型接口，对 Array 中的元素进行排序。
     * Params: array = 要排序的从零开始的一维 Array。
     *         comparer = 比较元素时使用的 IComparer(T) 泛型接口实现；
     *                                    如果为 null，则使用 DefaultComparer(T) 。
     * Comments: 此方法使用 QuickSort 算法。
     *           此实现执行不稳定排序；亦即，如果两元素相等，则其顺序可能不被保留。
     *           相反，稳定排序保留相等元素的顺序。
     */
    public static void sort(T)(T[] array, IComparer!(T) comparer = null)
    in
    {
        assert(array !is null);
    }
    body
    {

        static if( IsPointerType!(T) )
        {
            static assert(false, "Type " ~ T.stringof ~ " is not supported.");
        }
        else static if( IsArray!(T)  && !IsSomeString!(T) )
        {
            static assert(false, "Only support 1D array.");
        }
        else static if( is( T == struct ) && !( is ( typeof(T.opCmp) ) ) )
        {
            static assert(false, "Struct " ~ T.stringof ~ " should overload opCmp");
        }


        const int CUTOFF = 20;

        if ( comparer is null )
        {
            //下面这段代码由于内联，减少了函数调用次数和使用泛型进行字节交换等优化手段，性能提升不少。
            static if( IsIntegerType!(T) || IsCharType!(T) || ( is( T== struct ) && is( typeof(T.opCmp) ) ) )
            {

                T* low, high, mid, base, limit; 		//数组扫描和限制指针
                /*
                 * 模拟运行时堆栈
                 * 可由 1+log2(n) = 40来求得最终要排序的元素数量
                 * 40在万亿数量级上，对于任何数组都足够大，MSCRT中使用30
                 */
                T*[40] stack;
                T** stackPtr;                          	//栈顶指针

                //初始化各成员状态
                base = array.ptr;
                limit = base + array.length;    		//数组末端指针
                stackPtr = stack.ptr;               	//初始化栈顶指针

                while(true)                             //重复直到排序完成返回
                {
                    while(limit - base > CUTOFF)
                    {
                        //交换数组首值和中间值
                        mid = base + (limit - base) / 2;
                        swap(base, mid);

                        low = base + 1;     			//low从左到右扫描
                        high = limit - 1;     			//high从右到左扫描

                        //三路划分
                        //最后结果是 *low <= *base <= *high, *base是中值元素
                        if(*low > *high) swap(low, high);
                        if(*base > *high) swap(base, high);
                        if(*low > *base) swap(low, base);

                        while(true)
                        {
                            //移动low, 直到 *low >= pivot
                            do
                            {
                                low += 1;
                            }
                            while(*low < *base);

                            //移动high, 直到 *high <= pivot
                            do
                            {
                                high -= 1;
                            }
                            while(*high > *base);

                            //如果指针交叉则结束循环
                            if(low > high) break;

                            //否则交换元素继续扫描
                            swap(low, high);
                        }//while(true)

                        //移动中值到正确的位置上
                        swap(base, high);

                        //如果划分的左子数组比较大，则...
                        if( (high - base) > (limit - low) )
                        {
                            //入栈首尾两端指针
                            stackPtr[0] = base;
                            stackPtr[1] = high;
                            //排序右子数组
                            base = low;
                        }
                        else
                        {
                            stackPtr[0] = low;
                            stackPtr[1] = limit;
                            //排序左子数组
                            limit = high;
                        }

                        //栈顶指针增长
                        stackPtr += 2;

                        assert(stackPtr < stack.ptr + stack.length);
                    }//while(high - base > CUFOFF)

                    //插入排序剩余子数组
                    low = base + 1;
                    while(low < limit)
                    {
                        high = low;
                        while( (high > base) && ( *(high - 1) > *high) )
                        {
                            swap(high -1, high);
                            high -= 1;
                        }
                        low += 1;
                    }

                    //如果堆栈内还有内容
                    if(stackPtr > stack.ptr)
                    {
                        stackPtr -= 2;  //出栈 base，limit
                        base = stackPtr[0];
                        limit = stackPtr[1];
                    }
                    else
                        break;  				//否则堆栈内没有内容，排序完成
                }//while(true)

                return;
            }//static if( IsIntegerType!(T) || IsCharType!(T) )
            else
            {
                comparer = DefaultComparer!(T).getInstance();
            }
        }//if ( comparer is null )

        else
        {
            T* low, high, mid, base, limit; //数组扫描和限制指针
            /*
             * 模拟运行时堆栈
             * 可由 1+log2(n) = 40来求得最终要排序的元素数量
             * 40在万亿数量级上，对于任何数组都足够大，MSCRT中使用30
             */
            T*[40] stack;
            T** stackPtr;                      	//栈顶指针

            //初始化各成员状态
            base = array.ptr;
            limit = base + array.length;    	//数组末端指针
            stackPtr = stack.ptr;               //初始化栈顶指针

            while(true)                         //重复直到排序完成返回
            {
                while(limit - base > CUTOFF)
                {
                    //交换数组首值和中间值
                    mid = base + (limit - base) / 2;
                    swap(base, mid);

                    low = base + 1;     	//low从左到右扫描
                    high = limit - 1;     	//high从右到左扫描

                    //三路划分
                    //最后结果是 *low <= *base <= *high, *base是中值元素
                    if(comparer.compare(*low, *high) > 0) swap(low, high);
                    if(comparer.compare(*base, *high) > 0) swap(base, high);
                    if(comparer.compare(*low, *base) > 0) swap(low, base);

                    while(true)
                    {
                        //移动low, 直到 *low >= pivot
                        do
                        {
                            low += 1;
                        }
                        while(comparer.compare(*low, *base) < 0);

                        //移动high, 直到 *high <= pivot
                        do
                        {
                            high -= 1;
                        }
                        while(comparer.compare(*high, *base) > 0);

                        //如果指针交叉则结束循环
                        if(low > high) break;

                        //否则交换元素继续扫描
                        swap(low, high);
                    }//while(true)

                    //移动中值到正确的位置上
                    swap(base, high);

                    //如果划分的左子数组比较大，则...
                    if( (high - base) > (limit - low) )
                    {
                        //入栈首尾两端指针
                        stackPtr[0] = base;
                        stackPtr[1] = high;
                        //排序右子数组
                        base = low;
                    }
                    else
                    {
                        stackPtr[0] = low;
                        stackPtr[1] = limit;
                        //排序左子数组
                        limit = high;
                    }

                    //栈顶指针增长
                    stackPtr += 2;

                    assert(stackPtr < stack.ptr + stack.length);
                }//while(high - base > CUFOFF)

                //插入排序剩余子数组
                low = base + 1;
                while(low < limit)
                {
                    high = low;
                    while( (high > base) && ( comparer.compare(*(high - 1), *high) ) > 0 )
                    {
                        swap(high -1, high);
                        high -= 1;
                    }
                    low += 1;
                }

                //如果堆栈内还有内容
                if(stackPtr > stack.ptr)
                {
                    stackPtr -= 2;  //出栈 base，limit
                    base = stackPtr[0];
                    limit = stackPtr[1];
                }
                else
                    break;  //否则堆栈内没有内容，排序完成
            }//while(true)
        }
    }

    /**
     * 使用指定的委托对 Array 中的元素进行排序。
     * Params: array = 要排序的从零开始的一维 Array。
     *         comparison = 比较元素时要使用的委托。
     * Comments: 如果排序不能成功地完成，则结果未定义。
     *           此方法使用 QuickSort 算法。
     *           此实现执行不稳定排序；亦即，如果两元素相等，则其顺序可能不被保留。
     *           相反，稳定排序保留相等元素的顺序。
     */
	public static void sort(T)(T[] array, int delegate(T, T) comparison)
    in
    {
        assert( array !is null );
        assert( comparison !is null );
    }
    body
    {
        static if( IsPointerType!(T) )
        {
            static assert(false, "Type " ~ T.stringof ~ "is not supported.");
        }
        else static if( IsArray!(T)  && !IsSomeString!(T) )
        {
            static assert(false, "Only support 1D array.");
        }
        else static if( is( T == struct ) && !( is ( typeof(T.opCmp) ) ) )
        {
            static assert(false, "Struct " ~ T.stringof ~ " should overload opCmp");
        }

        const int CUTOFF = 20;

        T* low, high, mid, base, limit; //数组扫描和限制指针
        /*
         * 模拟运行时堆栈
         * 可由 1+log2(n) = 40来求得最终要排序的元素数量
         * 40在万亿数量级上，对于任何数组都足够大，MSCRT中使用30
         */
        T*[40] stack;
        T** stackPtr;                          //栈顶指针

        //初始化各成员状态
        base = array.ptr;
        limit = base + array.length;    //数组末端指针
        stackPtr = stack.ptr;               //初始化栈顶指针

        while(true)                             //重复直到排序完成返回
        {
            while(limit - base > CUTOFF)
            {
                //交换数组首值和中间值
                mid = base + (limit - base) / 2;
                swap(base, mid);

                low = base + 1;     //low从左到右扫描
                high = limit - 1;     //high从右到左扫描

                //三路划分
                //最后结果是 *low <= *base <= *high, *base是中值元素
                if(comparison(*low, *high) > 0) swap(low, high);
                if(comparison(*base, *high) > 0) swap(base, high);
                if(comparison(*low, *base) > 0) swap(low, base);

                while(true)
                {
                    //移动low, 直到 *low >= pivot
                    do
                    {
                        low += 1;
                    }
                    while(comparison(*low, *base) < 0);

                    //移动high, 直到 *high <= pivot
                    do
                    {
                        high -= 1;
                    }
                    while(comparison(*high, *base) > 0);

                    //如果指针交叉则结束循环
                    if(low > high) break;

                    //否则交换元素继续扫描
                    swap(low, high);
                }//while(true)

                //移动中值到正确的位置上
                swap(base, high);

                //如果划分的左子数组比较大，则...
                if( (high - base) > (limit - low) )
                {
                    //入栈首尾两端指针
                    stackPtr[0] = base;
                    stackPtr[1] = high;
                    //排序右子数组
                    base = low;
                }
                else
                {
                    stackPtr[0] = low;
                    stackPtr[1] = limit;
                    //排序左子数组
                    limit = high;
                }

                //栈顶指针增长
                stackPtr += 2;

                assert(stackPtr < stack.ptr + stack.length);
            }//while(high - base > CUFOFF)

            //插入排序剩余子数组
            low = base + 1;
            while(low < limit)
            {
                high = low;
                while( (high > base) && ( comparison(*(high - 1), *high) ) > 0 )
                {
                    swap(high -1, high);
                    high -= 1;
                }
                low += 1;
            }

            //如果堆栈内还有内容
            if(stackPtr > stack.ptr)
            {
                stackPtr -= 2;  //出栈 base，limit
                base = stackPtr[0];
                limit = stackPtr[1];
            }
            else
                break;  //否则堆栈内没有内容，排序完成
        }//while(true)
    }

    /// ditto
    public static void sort(T)(T[] array, int function(T, T) comparison)
    in
    {
        assert( array !is null );
        assert( comparison !is null );
    }
    body
    {
        static if( IsPointerType!(T) )
        {
            static assert(false, "Type " ~ T.stringof ~ "is not supported.");
        }
        else static if( IsArray!(T)  && !IsSomeString!(T) )
        {
            static assert(false, "Only support 1D array.");
        }
        else static if( is( T == struct ) && !( is ( typeof(T.opCmp) ) ) )
        {
            static assert(false, "Struct " ~ T.stringof ~ " should overload opCmp");
        }

        const int CUTOFF = 20;

        T* low, high, mid, base, limit; //数组扫描和限制指针
        /*
         * 模拟运行时堆栈
         * 可由 1+log2(n) = 40来求得最终要排序的元素数量
         * 40在万亿数量级上，对于任何数组都足够大，MSCRT中使用30
         */
        T*[40] stack;
        T** stackPtr;                          	//栈顶指针

        //初始化各成员状态
        base = array.ptr;
        limit = base + array.length;    		//数组末端指针
        stackPtr = stack.ptr;               	//初始化栈顶指针

        while(true)                             //重复直到排序完成返回
        {
            while(limit - base > CUTOFF)
            {
                //交换数组首值和中间值
                mid = base + (limit - base) / 2;
                swap(base, mid);

                low = base + 1;     //low从左到右扫描
                high = limit - 1;     //high从右到左扫描

                //三路划分
                //最后结果是 *low <= *base <= *high, *base是中值元素
                if(comparison(*low, *high) > 0) swap(low, high);
                if(comparison(*base, *high) > 0) swap(base, high);
                if(comparison(*low, *base) > 0) swap(low, base);

                while(true)
                {
                    //移动low, 直到 *low >= pivot
                    do
                    {
                        low += 1;
                    }
                    while(comparison(*low, *base) < 0);

                    //移动high, 直到 *high <= pivot
                    do
                    {
                        high -= 1;
                    }
                    while(comparison(*high, *base) > 0);

                    //如果指针交叉则结束循环
                    if(low > high) break;

                    //否则交换元素继续扫描
                    swap(low, high);
                }//while(true)

                //移动中值到正确的位置上
                swap(base, high);

                //如果划分的左子数组比较大，则...
                if( (high - base) > (limit - low) )
                {
                    //入栈首尾两端指针
                    stackPtr[0] = base;
                    stackPtr[1] = high;
                    //排序右子数组
                    base = low;
                }
                else
                {
                    stackPtr[0] = low;
                    stackPtr[1] = limit;
                    //排序左子数组
                    limit = high;
                }

                //栈顶指针增长
                stackPtr += 2;

                assert(stackPtr < stack.ptr + stack.length);
            }//while(high - base > CUFOFF)

            //插入排序剩余子数组
            low = base + 1;
            while(low < limit)
            {
                high = low;
                while( (high > base) && ( comparison(*(high - 1), *high) ) > 0 )
                {
                    swap(high -1, high);
                    high -= 1;
                }
                low += 1;
            }

            //如果堆栈内还有内容
            if(stackPtr > stack.ptr)
            {
                stackPtr -= 2;  //出栈 base，limit
                base = stackPtr[0];
                limit = stackPtr[1];
            }
            else
                break;  //否则堆栈内没有内容，排序完成
        }//while(true)
    }

    /**
     * 确定数组中的每个元素是否都与指定谓词定义的条件匹配。
     * Params: array = 要对照条件进行检查的从零开始的一维 Array.
     *         match = 定义检查元素时要对照的条件。
     * Returns: 如果 array 中的每个元素都与指定谓词定义的条件匹配，则为 true；否则为 false。
     *          如果数组中没有元素，则返回值为 true。
     */
    public static bool trueForAll(T)(T[] array, bool delegate(T) match)
    in
    {
        assert( array !is null );
        assert( match !is null );
    }
    body
    {
        for(auto i = 0; i < array.length; i++)
        {
            if( !match(array[i]) )
                return false;
        }
        return true;
    }
    /// ditto
    public static bool trueForAll(T)(T[] array, bool function(T) match)
    in
    {
        assert( array !is null );
        assert( match !is null );
    }
    body
    {
        for(auto i = 0; i < array.length; i++)
        {
            if( !match(array[i]) )
                return false;
        }
        return true;
    }


    //交换键-值对
    private static void swap(TKey, TValue)(TKey[] keys, TValue[] values, size_t i, size_t j)
    {
        TKey key = keys[i];
        keys[i] = keys[j];
        keys[j] = key;

        if (values !is null)
        {
            TValue value = values[i];
            values[i] = values[j];
            values[j] = value;
        }
    }
    //插入排序
    private static void insertSort(TKey, TValue)(TKey[] keys, TValue[] values, IComparer!(TKey) comparer)
    {
    	if(values !is null)
    	{
    	    for(auto i = 1; i < keys.length; i++)
            {
                TKey key = keys[i];
                TValue value = values[i];
                auto j = i;
                for(; j > 0 && comparer.compare(key, keys[j-1]) < 0; j--)
                {
                    keys[j] = keys[j-1];
    			    values[j] = values[j-1];
                }
                keys[j] = key;
                values[j] = value;
            }
    	}
    	else
    	{
    	    for(auto i = 1; i < keys.length; i++)
            {
                TKey key = keys[i];
                auto j = i;
                for(; j > 0 && comparer.compare(key, keys[j-1]) < 0; j--)
                {
                    keys[j] = keys[j-1];
                }
                keys[j] = key;
            }
    	}
    }
    /**
     * 基于第一个 Array 中的关键字，使用每个关键字的 IComparable(T) 泛型接口实现，对两个 Array 对象（一个包含关键字，另一个包含对应的项）进行排序。
     * Params:
     * 		keys = 一维 Array，它包含要排序的关键字。
     * 		items = 一维 Array，其中包含与 keys 中的关键字对应的项；如果为 null ，则只对 keys 进行排序。
     * Comments:
     * 		此方法使用 QuickSort 算法。
     * 		一般情况下，此方法的运算复杂度为 O(n log n)，其中 n 是 array 的 length；最坏的情况下其运算复杂度为 O(n ^ 2)。
     */
    public static void sort(TKey, TValue)(TKey[] keys, TValue[] items, IComparer!(TKey) comparer = null)
    in
    {
        assert( keys !is null && keys.length == items.length);
    }
    body
    {
        static if( IsPointerType!(TKey) )
        {
            static assert(false, "Type " ~ TKey.stringof ~ "is not supported.");
        }
        else static if( IsArray!(TKey)  && !IsSomeString!(TKey) )
        {
            static assert(false, "Only support 1D array.");
        }
        else static if( is( TKey == struct ) && !( is ( typeof(TKey.opCmp) ) ) )
        {
            static assert(false, "Struct " ~ TKey.stringof ~ " should overload opCmp");
        }

        const CUTOFF = 20;

        if( comparer is null )
            comparer = DefaultComparer!(TKey).getInstance();

        auto low = 0;
        auto high = keys.length - 1;

        if(low + CUTOFF > high)
        {
        	insertSort!(TKey, TValue)(keys, items, comparer);
        }
        else
        {

        auto mid = low + (high-low) / 2;

        if( comparer.compare( keys[mid], keys[low] ) < 0 )
            swap!(TKey, TValue)( keys, items, low, mid );
        if( comparer.compare( keys[high], keys[low] ) < 0 )
            swap!(TKey, TValue)( keys, items, low, high );
        if( comparer.compare( keys[high], keys[mid] ) < 0 )
            swap!(TKey, TValue)( keys, items, mid, high );

        //Place pivot at position high-1
        swap!(TKey, TValue)( keys, items, mid, high-1 );

        TKey keyPivot = keys[high-1];

        //Begin partitioning
        size_t i, j;
        for( i = low, j = high-1; ; )
        {
            while(comparer.compare(keys[++i], keyPivot) < 0)
            {}
            while(comparer.compare(keyPivot, keys[--j]) < 0)
            {}

            if( i >= j )
                break;

            swap!(TKey, TValue)(keys, items, i, j);
        }

        swap!(TKey, TValue)(keys, items, i, high-1);

        sort!(TKey, TValue)(keys[low..i], items[low..i], comparer);         	//Sort small elements
        sort!(TKey, TValue)(keys[i+1..high+1], items[i+1..high+1], comparer);    		//Sort large elements
        }
    }
}

unittest
{
    int[5] array = [1,2,3,3,4];

    assert( Array.binarySearch!(int)(array, 4) == 4 );
    assert( Array.indexOf!(int)(array, 2) == 1 );
    assert( Array.lastIndexOf!(int)(array, 3) == 3 );
    assert( Array.indexOf!(int)(array, 5) == -1 );

    Object[] arrayObject = new Object[3];
    arrayObject[0] = null;
    arrayObject[1] = new Object();
    arrayObject[2] = null;

    assert( Array.indexOf!(Object)(arrayObject, null) == 0 );

    Random random = new Random();

    int[] intArray = new int[100];
    for(auto i = 0; i < intArray.length; i++)
    {
        intArray[i] = random.next();
    }

    Array.sort!(int)(intArray);

    for(auto i = 0; i < intArray.length-1; i++)
    {
        assert( intArray[i] <= intArray[i+1] );
    }

    double[2] a = [0.4, 0.3];
    int[2] b = [4,7];

    Array.sort!(double, int)(a, b);

    assert(a[0] == 0.3);
    assert(a[1] == 0.4);
    assert(b[0] == 7);
    assert(b[1] == 4);

    double[21] c = [0.20,0.19,0.18,0.17,0.16,0.15,0.14,0.13,0.12,0.11,0.10,0.09,0.08,0.07,0.06,0.05,0.04,0.03,0.02,0.01, 0.00];
    int[21] d = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];

    Array.sort!(double,int)(c, d);

    assert(c[0] == 0.00);
    assert(c[1] == 0.01);
    assert(c[2] == 0.02);
    assert(c[3] == 0.03);
    assert(c[4] == 0.04);
    assert(c[5] == 0.05);
    assert(c[6] == 0.06);
    assert(c[7] == 0.07);
    assert(c[8] == 0.08);
    assert(c[9] == 0.09);
    assert(c[10] == 0.10);
    assert(c[11] == 0.11);
    assert(c[12] == 0.12);
    assert(c[13] == 0.13);
    assert(c[14] == 0.14);
    assert(c[15] == 0.15);
    assert(c[16] == 0.16);
    assert(c[17] == 0.17);
    assert(c[18] == 0.18);
    assert(c[19] == 0.19);
    assert(c[20] == 0.20);


    assert(d[0] == 20);
    assert(d[1] == 19);
    assert(d[2] == 18);
    assert(d[3] == 17);
    assert(d[4] == 16);
    assert(d[5] == 15);
    assert(d[6] == 14);
    assert(d[7] == 13);
    assert(d[8] == 12);
    assert(d[9] == 11);
    assert(d[10] == 10);
    assert(d[11] == 9);
    assert(d[12] == 8);
    assert(d[13] == 7);
    assert(d[14] == 6);
    assert(d[15] == 5);
    assert(d[16] == 4);
    assert(d[17] == 3);
    assert(d[18] == 2);
    assert(d[19] == 1);
    assert(d[20] == 0);
}
